﻿//#include<iostream>
//#include<string>
//#include<cstring>
//using namespace std;
//const int MaxW = 9999999; 
//// 定义huffman树结点类
//class HuffNode
//{
//public:
//    int weight;     // 权值
//    int parent;     // 父结点下标
//    int leftchild;  // 左孩子下标
//    int rightchild; // 右孩子下标
//};
//// 定义赫夫曼树类
//class HuffMan
//{
//private:
//    void MakeTree();    // 建树，私有函数，被公有函数调用
//    void SelectMin(int pos, int* s1, int* s2);  // 从 1 到 pos 的位置找出权值最小的两个结点，把结点下标存在 s1 和 s2 中
//public:
//    int len;    // 结点数量
//    int lnum;   // 叶子数量
//    HuffNode* huffTree; // 赫夫曼树，用数组表示
//    string* huffCode;   // 每个字符对应的赫夫曼编码
//    void MakeTree(int n, int wt[]); // 公有函数，被主函数main调用
//    void Coding();  // 公有函数，被主函数main调用
//    void Destroy();
//};
//// 构建huffman树
//void HuffMan::MakeTree(int n, int wt[])
//{
//    // 参数是叶子结点数量和叶子权值
//    // 公有函数，对外接口
//    int i;
//    lnum = n;
//    len = 2 * n - 1;
//    huffTree = new HuffNode[2 * n];
//    huffCode = new string[lnum + 1];    // 位置从 1 开始计算
//    // huffCode实质是个二维字符数组，第 i 行表示第 i 个字符对应的编码
//    // 赫夫曼树huffTree初始化
//    for (i = 1; i <= n; i++)
//        huffTree[i].weight = wt[i - 1]; // 第0号不用，从1开始编号
//    for (i = 1; i <= len; i++)
//    {
//        if (i > n) huffTree[i].weight = 0;  // 前n个结点是叶子，已经设置
//        huffTree[i].parent = 0;
//        huffTree[i].leftchild = 0;
//        huffTree[i].rightchild = 0;
//    }
//    MakeTree();  // 调用私有函数建树
//}
//void HuffMan::SelectMin(int pos, int* s1, int* s2)
//{
//    // 找出最小的两个权值的下标
//    // 函数采用地址传递的方法，找出两个下标保存在 s1 和 s2 中
//    int w1, w2, i;
//    w1 = w2 = MaxW;  // 初始化w1和w2为最大值，在比较中会被实际的权值替换
//    *s1 = *s2 = 0;
//    for (i = 1; i <= pos; i++)
//    {
//        // 比较过程如下：
//        // 如果第 i 个结点的权值小于 w1，且第 i 个结点是未选择的结点，提示：如果第 i 结点未选择，它父亲为 0
//        // 把第 w1 和 s1 保存到 w2 和 s2，即原来的第一最小值变成第二最小值
//        // 把第 i 结点的权值和下标保存到 w1 和 s1，作为第一最小值
//        // 否则，如果第 i 结点的权值小于 w2，且第 i 结点是未选择的结点
//        // 把第 i 结点的权值和下标保存到 w2 和 s2，作为第二最小值
//        if (huffTree[i].weight < w1 && huffTree[i].parent == 0)
//        {
//            w2 = w1;
//            *s2 = *s1;
//            w1 = huffTree[i].weight;
//            *s1 = i;
//        }
//        else if(huffTree[i].weight < w2 && huffTree[i].parent == 0)
//        {
//            w2 = huffTree[i].weight;
//            *s2 = i;
//        }
//    }
//}
//void HuffMan::MakeTree()
//{
//    // 私有函数，被公有函数调用
//    int i, s1, s2;
//    for (i = lnum + 1; i <= len; i++)
//    {
//        SelectMin(i - 1, &s1, &s2);  // 找出两个最小权值的下标放入 s1 和 s2 中
//        // 将找出的两棵权值最小的子树合并为一棵子树，过程包括
//        // 结点 s1 和结点 s2 的父亲设为 i
//        // 结点 i 的左右孩子分别设为 s1 和 s2
//        // 结点 i 的权值等于 s1 和 s2 的权值和
//        huffTree[s1].parent = i;
//        huffTree[s2].parent = i;
//        huffTree[i].leftchild = s1;
//        huffTree[i].rightchild = s2;
//        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
//    }
//}
//// 销毁赫夫曼树
//void HuffMan::Destroy()
//{
//    len = 0;
//    lnum = 0;
//    delete[]huffTree;
//    delete[]huffCode;
//}
//// 赫夫曼编码
//void HuffMan::Coding()
//{
//    char* cd;
//    int i, c, f, start;
//    // 求 n 个结点的赫夫曼编码
//    cd = new char[lnum];    // 分配求编码的工作空间
//    cd[lnum - 1] = '\0';    // 编码结束符
//    for (i = 1; i <= lnum; ++i)
//    {
//        // 逐个字符求赫夫曼编码
//        start = lnum - 1;   // 编码结束符位置
//        // 参考课本P147算法6.12 HuffmanCoding代码
//        c = i;
//        f = huffTree[c].parent;
//        while (f != 0)
//        {
//            if (huffTree[f].leftchild == c)
//                cd[--start] = '0';
//            else
//                cd[--start] = '1';
//            c = f;
//            f = huffTree[c].parent;
//        }
//        huffCode[i]=string(&cd[start]);
//    }
//    delete[]cd;    // 释放工作空间
//}
//// 主函数
//int main()
//{
//    //主函数根据需要添加代码
//    int t, n, i, j;
//    int wt[800];
//    HuffMan myHuff;
//    cin >> t;
//    for (i = 0; i < t; i++)
//    {
//        cin >> n;
//        int* wt = new int[n];
//        for (int k = 0; k < n; k++)
//        {
//            cin>> wt[k];
//        }
//        HuffMan myHuff;
//        myHuff.MakeTree(n, wt); 
//        myHuff.Coding();
//        for (j = 1; j <= n; j++)
//        {
//            cout << myHuff.huffTree[j].weight << '-';   // 输出各权值
//            cout << myHuff.huffCode[j] << endl; // 输出各编码
//        }
//        myHuff.Destroy();
//        delete[]wt;
//    }
//    return 0;
//}
//#include<iostream>
//#include<string>
//#include<cstring>
//using namespace std;
//const int MaxW = 9999999;
//// 定义huffman树结点类
//class HuffNode
//{
//public:
//    int weight;     // 权值
//    int parent;     // 父结点下标
//    int leftchild;  // 左孩子下标
//    int rightchild; // 右孩子下标
//};
//// 定义赫夫曼树类
//class HuffMan
//{
//private:
//    void MakeTree();    // 建树，私有函数，被公有函数调用
//    void SelectMin(int pos, int* s1, int* s2);  // 从 1 到 pos 的位置找出权值最小的两个结点，把结点下标存在 s1 和 s2 中
//public:
//    int len;    // 结点数量
//    int lnum;   // 叶子数量
//    char* str_;
//    HuffNode* huffTree; // 赫夫曼树，用数组表示
//    string* huffCode;   // 每个字符对应的赫夫曼编码
//    void MakeTree(int n, int wt[],char str[]); // 公有函数，被主函数main调用
//    void Coding();  // 公有函数，被主函数main调用
//    bool Decode(const string codestr, char txtstr[]);
//    void Destroy();
//};
//// 构建huffman树
//void HuffMan::MakeTree(int n, int wt[],char str[])
//{
//    // 参数是叶子结点数量和叶子权值
//    // 公有函数，对外接口
//    int i;
//    lnum = n;
//    len = 2 * n - 1;
//    huffTree = new HuffNode[2 * n];
//    huffCode = new string[lnum + 1];    // 位置从 1 开始计算
//    str_ = new char[lnum + 1];
//    // huffCode实质是个二维字符数组，第 i 行表示第 i 个字符对应的编码
//    // 赫夫曼树huffTree初始化
//    for (i = 1; i <= n; i++)
//    {
//        huffTree[i].weight = wt[i - 1]; // 第0号不用，从1开始编号
//        str_[i] = str[i - 1];
//    }
//    for (i = 1; i <= len; i++)
//    {
//        if (i > n) huffTree[i].weight = 0;  // 前n个结点是叶子，已经设置
//        huffTree[i].parent = 0;
//        huffTree[i].leftchild = 0;
//        huffTree[i].rightchild = 0;
//    }
//    MakeTree();  // 调用私有函数建树
//}
//void HuffMan::SelectMin(int pos, int* s1, int* s2)
//{
//    // 找出最小的两个权值的下标
//    // 函数采用地址传递的方法，找出两个下标保存在 s1 和 s2 中
//    int w1, w2, i;
//    w1 = w2 = MaxW;  // 初始化w1和w2为最大值，在比较中会被实际的权值替换
//    *s1 = *s2 = 0;
//    for (i = 1; i <= pos; i++)
//    {
//        // 比较过程如下：
//        // 如果第 i 个结点的权值小于 w1，且第 i 个结点是未选择的结点，提示：如果第 i 结点未选择，它父亲为 0
//        // 把第 w1 和 s1 保存到 w2 和 s2，即原来的第一最小值变成第二最小值
//        // 把第 i 结点的权值和下标保存到 w1 和 s1，作为第一最小值
//        // 否则，如果第 i 结点的权值小于 w2，且第 i 结点是未选择的结点
//        // 把第 i 结点的权值和下标保存到 w2 和 s2，作为第二最小值
//        if (huffTree[i].weight < w1 && huffTree[i].parent == 0)
//        {
//            w2 = w1;
//            *s2 = *s1;
//            w1 = huffTree[i].weight;
//            *s1 = i;
//        }
//        else if (huffTree[i].weight < w2 && huffTree[i].parent == 0)
//        {
//            w2 = huffTree[i].weight;
//            *s2 = i;
//        }
//    }
//}
//void HuffMan::MakeTree()
//{
//    // 私有函数，被公有函数调用
//    int i, s1, s2;
//    for (i = lnum + 1; i <= len; i++)
//    {
//        SelectMin(i - 1, &s1, &s2);  // 找出两个最小权值的下标放入 s1 和 s2 中
//        // 将找出的两棵权值最小的子树合并为一棵子树，过程包括
//        // 结点 s1 和结点 s2 的父亲设为 i
//        // 结点 i 的左右孩子分别设为 s1 和 s2
//        // 结点 i 的权值等于 s1 和 s2 的权值和
//        huffTree[s1].parent = i;
//        huffTree[s2].parent = i;
//        huffTree[i].leftchild = s1;
//        huffTree[i].rightchild = s2;
//        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
//    }
//}
//// 销毁赫夫曼树
//void HuffMan::Destroy()
//{
//    len = 0;
//    lnum = 0;
//    delete[]huffTree;
//    delete[]huffCode;
//}
//// 赫夫曼编码
//void HuffMan::Coding()
//{
//    char* cd;
//    int i, c, f, start;
//    // 求 n 个结点的赫夫曼编码
//    cd = new char[lnum];    // 分配求编码的工作空间
//    cd[lnum - 1] = '\0';    // 编码结束符
//    for (i = 1; i <= lnum; ++i)
//    {
//        // 逐个字符求赫夫曼编码
//        start = lnum - 1;   // 编码结束符位置
//        // 参考课本P147算法6.12 HuffmanCoding代码
//        c = i;
//        f = huffTree[c].parent;
//        while (f != 0)
//        {
//            if (huffTree[f].leftchild == c)
//                cd[--start] = '0';
//            else
//                cd[--start] = '1';
//            c = f;
//            f = huffTree[c].parent;
//        }
//        huffCode[i] = string(&cd[start]);
//    }
//    delete[]cd;    // 释放工作空间
//}bool HuffMan::Decode(const string codestr, char txtstr[])
//{
//    // 编码串是codestr，解码结果放在 txtstr 中
//    // 编码 0 表示往左孩子移动，编码 1 表示往右孩子移动
//    int i, k, c;
//    char ch;
//    c = len; // c表示结点数组下标
//    // 根结点是结点数组的最后一个结点，所以 c 一开始指向根节点
//    k = 0;  // txtstr的指针
//    for (i = 0; i < codestr.length(); i++)
//    {
//        // 解码流程如下：
//        // 取编码串的第 i 个字符放入变量ch
//        // 如果 ch 是字符 0 ，表示往左孩子移动，则 c 跳转到左孩子
//        // 如果 ch 是字符 1 ，表示往右孩子移动，则 c 跳转到右孩子
//        // 如果 ch 非 0 非 1 ，表示编码串有错误，返回 error 表示解码失败
//        // 如果 c 指向的结点是叶子
//            // 解码串 txtstr 的第 k 位置保存结点 c 内的字符
//            // k ++
//            // c 跳回根节点
//        // 否则
//            // ch = '\0';   // 设置 ch 值是用于检查不完整编码的报错
//        ch = codestr[i];
//        if (ch == '0')
//        {
//            c = huffTree[c].leftchild;
//        }
//        else if (ch == '1')
//        {
//            c = huffTree[c].rightchild;
//        }
//        else
//        {
//            return false;
//            break;
//        }
//        if (huffTree[c].leftchild == 0 && huffTree[c].rightchild == 0)
//        {
//            txtstr[k] = str_[c];
//            k++;
//            c = len;
//        }
//    }
//    if (c != len) 
//        return false;
//    else
//    txtstr[k] = '\0'; 
//    return true;
//}
//
//int main()
//{
//    int t, n, i, j,m,ch;
//    string codestr;
//    int wt[800];
//    HuffMan myHuff;
//    cin >> t;
//    for (i = 0; i < t; i++)
//    {
//        cin >> n;
//        int* wt = new int[n];
//        for (int k = 0; k < n; k++)
//        {
//            cin >> wt[k];
//        }
//        HuffMan myHuff;
//        char* str = new char[n];
//        for (int k = 0; k <n; k++)
//        {
//            cin >> str[k];
//        }
//        cin >> m;
//        myHuff.MakeTree(n, wt, str);
//        for (int j = 0; j < m; j++)
//        {
//            cin >> codestr;
//            char txtstr[10000] = { 0 };
//            if (myHuff.Decode(codestr, txtstr))
//            {
//                cout << txtstr << endl;
//            }
//            else
//                cout << "error" << endl;
//        }
//        myHuff.Destroy();
//        delete[] wt;
//        delete[] str;
//    }
//    return 0;
//}
//#include <iostream>
//using namespace std;
//typedef struct BTnode
//{
//	int data;
//	struct BTnode* left;
//	struct BTnode* right;
//}BTnode;
//BTnode* buytree(int x)
//{
//	BTnode* node= new BTnode;
//	node->data = x;
//	node->left = NULL;
//	node->right = NULL;
//	return node;
//}
//BTnode* inordercreatetree(int* arr,int* i)
//{
//	if (arr == NULL)
//	{
//		return NULL;
//	}
//	else
//	{
//		BTnode* node = buytree(arr[*i]);
//		node->left= inordercreatetree(arr, i);
//		*i++;
//		node->right = inordercreatetree(arr, i);
//		return node;
//	}
//}
//BTnode* postordercreatetree(int* arr, int* i)
//{
//	if (arr == NULL)
//	{
//		return NULL;
//	}
//	else
//	{
//		BTnode* node = buytree(arr[*i]);
//		node->left = inordercreatetree(arr, i);
//		*i++;
//		node->right = inordercreatetree(arr, i);
//		return node;
//	}
//}
//int main()
//{
//	int t, n;
//	cin >> t;
//	for (int i = 0; i < t; i++)
//	{
//		cin >> n;
//		int* inorderarr = new int[n];
//		int* postorderarr = new int[n];
//		for (int j = 0; j < n; j++)
//		{
//			cin >> inorderarr[i];
//			cin >> postorderarr[i];
//		}
//		int k1 = 0, k2 = 0;
//		BTnode* root1 = inordercreatetree(inorderarr, &k1);
//		BTnode* root2 = postordercreatetree(postorderarr, &k2);
//	}
//	

//#include<iostream>
//#include<string>
//#include<cstring>
//using namespace std;
//const int MaxW = 9999999;
//// 定义huffman树结点类
//class HuffNode
//{
//public:
//    int weight;     // 权值
//    int parent;     // 父结点下标
//    int leftchild;  // 左孩子下标
//    int rightchild; // 右孩子下标
//};
//// 定义赫夫曼树类
//class HuffMan
//{
//private:
//    void MakeTree();    // 建树，私有函数，被公有函数调用
//    void SelectMin(int pos, int* s1, int* s2);  // 从 1 到 pos 的位置找出权值最小的两个结点，把结点下标存在 s1 和 s2 中
//public:
//    int len;    // 结点数量
//    int lnum;   // 叶子数量
//    HuffNode* huffTree; // 赫夫曼树，用数组表示
//    string* huffCode;   // 每个字符对应的赫夫曼编码
//    void MakeTree(int n, int wt[]); // 公有函数，被主函数main调用
//    void Coding();  // 公有函数，被主函数main调用
//    void Destroy();
//};
//// 构建huffman树
//void HuffMan::MakeTree(int n, int wt[])
//{
//    // 参数是叶子结点数量和叶子权值
//    // 公有函数，对外接口
//    int i;
//    lnum = n;
//    len = 2 * n - 1;
//    huffTree = new HuffNode[2 * n];
//    huffCode = new string[lnum + 1];    // 位置从 1 开始计算
//    // huffCode实质是个二维字符数组，第 i 行表示第 i 个字符对应的编码
//    // 赫夫曼树huffTree初始化
//    for (i = 1; i <= n; i++)
//        huffTree[i].weight = wt[i - 1]; // 第0号不用，从1开始编号
//    for (i = 1; i <= len; i++)
//    {
//        if (i > n) huffTree[i].weight = 0;  // 前n个结点是叶子，已经设置
//        huffTree[i].parent = 0;
//        huffTree[i].leftchild = 0;
//        huffTree[i].rightchild = 0;
//    }
//    MakeTree();  // 调用私有函数建树
//}
//void HuffMan::SelectMin(int pos, int* s1, int* s2)
//{
//    // 找出最小的两个权值的下标
//    // 函数采用地址传递的方法，找出两个下标保存在 s1 和 s2 中
//    int w1, w2, i;
//    w1 = w2 = MaxW;  // 初始化w1和w2为最大值，在比较中会被实际的权值替换
//    *s1 = *s2 = 0;
//    for (i = 1; i <= pos; i++)
//    {
//        // 比较过程如下：
//        // 如果第 i 个结点的权值小于 w1，且第 i 个结点是未选择的结点，提示：如果第 i 结点未选择，它父亲为 0
//        // 把第 w1 和 s1 保存到 w2 和 s2，即原来的第一最小值变成第二最小值
//        // 把第 i 结点的权值和下标保存到 w1 和 s1，作为第一最小值
//        // 否则，如果第 i 结点的权值小于 w2，且第 i 结点是未选择的结点
//        // 把第 i 结点的权值和下标保存到 w2 和 s2，作为第二最小值
//        if (huffTree[i].weight < w1 && huffTree[i].parent == 0)
//        {
//            w2 = w1;
//            *s2 = *s1;
//            w1 = huffTree[i].weight;
//            *s1 = i;
//        }
//        else if (huffTree[i].weight < w2 && huffTree[i].parent == 0)
//        {
//            w2 = huffTree[i].weight;
//            *s2 = i;   
//        }
//    }
//}
//void HuffMan::MakeTree()
//{
//    // 私有函数，被公有函数调用
//    int i, s1, s2;
//    for (i = lnum + 1; i <= len; i++)
//    {
//        SelectMin(i - 1, &s1, &s2);  // 找出两个最小权值的下标放入 s1 和 s2 中
//        // 将找出的两棵权值最小的子树合并为一棵子树，过程包括
//        // 结点 s1 和结点 s2 的父亲设为 i
//        // 结点 i 的左右孩子分别设为 s1 和 s2
//        // 结点 i 的权值等于 s1 和 s2 的权值和
//        huffTree[s1].parent = i;
//        huffTree[s2].parent = i;
//        huffTree[i].leftchild = s1;
//        huffTree[i].rightchild = s2;
//        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
//    }
//}
//// 销毁赫夫曼树
//void HuffMan::Destroy()
//{
//    len = 0;
//    lnum = 0;
//    delete[]huffTree;
//    delete[]huffCode;
//}
//// 赫夫曼编码
//void HuffMan::Coding()
//{
//    char* cd;
//    int i, c, f, start;
//    int count = 0;
//    // 求 n 个结点的赫夫曼编码
//    cd = new char[lnum];    // 分配求编码的工作空间
//    cd[lnum - 1] = '\0';    // 编码结束符
//    for (i = 1; i <= lnum; ++i)
//    {
//        // 逐个字符求赫夫曼编码
//        start = lnum - 1;   // 编码结束符位置
//        // 参考课本P147算法6.12 HuffmanCoding代码
//        c = i;
//        f = huffTree[c].parent;
//        while (f != 0)
//        {
//            if (huffTree[f].leftchild == c)
//            {
//                cd[--start] = '0';
//            }
//            else
//            {
//                cd[--start] = '1';
//            }
//            c = f;
//            f = huffTree[c].parent;
//        }
//        huffCode[i] = string(&cd[start]);
//        count+= huffTree[i].weight * huffCode[i].length();
//    }
//    cout << count << endl;
//    delete[]cd;    // 释放工作空间
//}
//// 主函数
//int main()
//{
//    //主函数根据需要添加代码
//    int t, n, i, j;
//    int wt[800];
//    HuffMan myHuff;
//    string str;
//    cin >> t;
//    for (i = 0; i < t; i++)
//    {
//        cin >> str;
//        int n = str.length();
//        string str_;//存储不同字符ABCDEF
//        for (int k = 0; k < n; k++)
//        {
//            int flag = 1;
//            for (int j = 0; j < str_.length(); j++)
//            {
//                if (str[k] == str_[j])
//                {
//                    flag = 0;
//                    break;
//                }
//            }
//            if (flag == 1)
//            {
//                str_ += str[k];
//            }
//        }
//        int* wt = new int[str_.size()];//计算每个字符出现的频率权重
//        for (int k = 0; k < str_.size(); k++)
//        {
//            char ch = str_[k];
//            int num = 0;
//            for (int j = 0; j < n; j++)
//            {
//                if (str[j] == ch)
//                {
//                    num++;
//                }
//            }
//            wt[k] = num;
//        }
//        if (str_.size() == 1)
//        {
//            cout << n << endl;
//            continue;
//        }
//        HuffMan myHuff;
//        myHuff.MakeTree(str_.size(), wt);
//        myHuff.Coding();
//        myHuff.Destroy();
//        delete[]wt;
//    }
//    return 0;
//}
//#include<iostream>
//#include<string>
//#include<cstring>
//using namespace std;
//class BTNode
//{
//public:
//    int data;
//    BTNode* left;
//    BTNode* right;
//    BTNode()
//    {
//        left = NULL;
//        right = NULL;
//    }
//    BTNode(int x)
//    {
//        data = x;
//        left =NULL;
//        right = NULL;
//    }
//    BTNode* createtree(int* s1, int* s2,int n)
//    {
//        if (n==0)
//        {
//            return NULL;
//        }
//        else
//        {
//            int j;
//            int root_ = s2[n - 1];
//            BTNode* root = new BTNode(root_);
//            for (j = 0; s1[j] != root_; j++) {};//找到j的位置
//            root->left = createtree(s1, s2, j);//左子树
//            root->right = createtree(s1 + j + 1, s2 + j, n - j - 1);//右子树
//            return root;
//        }
//    }
//    void checkmin(BTNode* root,int* min)
//    {
//        if (root == NULL)
//            return;
//        else
//        {
//            if (root->left == NULL && root->right == NULL)
//            {
//                if (root->data < *min)
//                {
//                    *min = root->data;
//                }
//                return;
//            }
//             checkmin(root->left, min);
//             checkmin(root->right, min);
//        }
//    }
//    void Destroy(BTNode* root)
//    {
//        if (root == NULL)
//            return;
//        else
//        {
//            Destroy(root->left);
//            Destroy(root->right);
//            delete root;
//        }
//    }
//};
//int main()
//{
//    int t, n;
//    int intree, posttree;
//    cin >> t;
//    for (int i = 0; i < t; i++)
//    {
//        cin >> n;
//        int* intree = new int[n];
//        int* posttree = new int[n];
//        for (int j = 0; j < n; j++)
//        {
//            cin >> intree[j];
//        }
//        for (int k = 0; k < n; k++)
//        {
//            cin >> posttree[k];
//        }
//        BTNode node;
//        BTNode* root=node.createtree(intree, posttree,n);
//        int min = intree[0];
//        for (int k = 0; k < n; k++)
//        {
//            if (intree[k] > min)
//            {
//                min = intree[k];
//            }
//        }
//        node.checkmin(root, &min);
//        cout << min << endl;
//        node.Destroy(root);
//    }
//    return 0;
//}
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
class BTNode
{
public:
    int weight;
    char data;
    BTNode* left;
    BTNode* right;
    BTNode()
    {
        weight = 0;
        left = NULL;
        right = NULL;
    }
    BTNode(char x)
    {
        data = x;
        weight = 0;
        left = NULL;
        right = NULL;
    }
    BTNode* createtree(string str,int* i)
    {
        if (str[*i] == '0'||*i>=str.size())
        {
            (*i)++;
            return NULL;
        }
        else
        {
            BTNode* node =new BTNode(str[*i]);
            (*i)++;
            node->left = createtree(str, i);
            node->right = createtree(str, i);
            return node;
        }
    }
    void Weight(BTNode* root,int wt[],int* j)
    {
        if (root == NULL)
        {
            return;
        }
        else
        {
            root->weight = wt[(*j)++];
            Weight(root->left, wt,j);
            Weight(root->right, wt,j);
        }
    }
    int height(BTNode* root)
    {
        if (root == NULL)
            return 0;
        else
        {
            return max(height(root->left), height(root->right)) + root->weight;
        }
    }
    void Destroy(BTNode* root)
    {
        if (root == NULL)
            return;
        else
        {
            Destroy(root->left);
            Destroy(root->right);
            delete root;
        }
    }
};
int main()
{
    int t, n;
    string str;
    cin >> t;
   
    for (int i = 0; i < t; i++)
    { 
       cin.ignore();//清除缓存区
        BTNode node;
        getline(cin,str);
        cin >> n;
        int* wt = new int[n];
        for (int j = 0; j < n; j++)
        {
            cin >> wt[j];
        }
        int k = 0, j = 0;
        BTNode* root = node.createtree(str, &k);
        node.Weight(root, wt,&j);
        int maxheight = node.height(root);
        cout << maxheight << endl;
        delete[]wt;
        node.Destroy(root);
    }
    return 0;
}